#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdio.h>
#include <ctype.h>
#include <math.h>

#include "lexical.h"

static const OPERATOR operators[] = {
	/* 算数运算 */
	{2, 17, 1, left2right, oper_lparen},	 // 左括号
	{2, 17, 17, left2right, oper_rparen},	 // 右括号
	{2, 12, 12, left2right, oper_plus},		 // 加
	{2, 12, 12, left2right, oper_minus},	 // 减
	{2, 13, 13, left2right, oper_multiply},	 // 乘
	{2, 13, 13, left2right, oper_divide},	 // 除
	{2, 13, 13, left2right, oper_mod},		 // 模
	{2, 14, 14, left2right, oper_power},	 // 幂
	{1, 16, 15, right2left, oper_positive},	 // 正号
	{1, 16, 15, right2left, oper_negative},	 // 负号
	{1, 16, 15, left2right, oper_factorial}, // 阶乘
	/* 关系运算 */
	{2, 10, 10, left2right, oper_lt}, // 小于
	{2, 10, 10, left2right, oper_gt}, // 大于
	{2, 9, 9, left2right, oper_eq},	  // 等于
	{2, 9, 9, left2right, oper_ne},	  // 不等于
	{2, 10, 10, left2right, oper_le}, // 不大于
	{2, 10, 10, left2right, oper_ge}, // 不小于
	/* 逻辑运算 */
	{2, 5, 5, left2right, oper_and},   // 且
	{2, 4, 4, left2right, oper_or},	   // 或
	{1, 15, 15, right2left, oper_not}, // 非
	/* 赋值 */
	// BASIC 表达式中不会出现赋值
	{2, 2, 2, right2left, oper_assignment}, // 赋值
	/* 最小优先级 */
	{2, 0, 0, right2left, oper_min} // 栈底
};

static const char *h;
static const char *e;
static TOKEN before;

static TOKEN next_token()
{
	TOKEN token = {0};
	STRING s;
	int i;

	if (e == NULL) // 当前表达式
	{
		return token;
	}

	// 去掉前导空格
	while (*e && isspace(*e))
	{
		e++;
	}

	if (*e == 0)
	{
		return token;
	}

	if (*e == '"') // 如果是引号开头
	{
		token.type = token_operand;	 // 说明是操作数
		token.var.type = var_string; // 而且还是字符串
		e++;
		for (i = 0; *e && *e != '"'; i++) // 遍历这个字符串，直到碰到下一个双引号
		{
			token.var.s[i] = *e; // 将双引号里面内容保存起来
			e++;				 // 指向下一个字符
		}
		e++;
	}
	else if (isalpha(*e)) // 如果是字母
	{
		token.type = token_operator;  // 操作符
		for (i = 0; isalnum(*e); i++) // 检测字符串是否由字母和数字组成
		{
			s[i] = toupper(*e); // 转换为大写字母
			e++;
		}
		s[i] = 0;
		if (!strcmp(s, "AND"))
		{
			token.ator = operators[oper_and];
		}
		else if (!strcmp(s, "OR"))
		{
			token.ator = operators[oper_or];
		}
		else if (!strcmp(s, "NOT"))
		{
			token.ator = operators[oper_not];
		}
		else if (i == 1) // 数字
		{
			token.type = token_operand;		// 操作数
			token.var = memory[s[0] - 'A']; // 变量
			if (token.var.type == var_null)
			{
				memset(&token, 0, sizeof(token));
				fprintf(stderr, "变量%c未赋值！\n", s[0]);
				exit(EXIT_FAILURE);
			}
		}
		else
		{
			goto errorhandler;
		}
	}
	else if (isdigit(*e) || *e == '.') // 数字或者小数点
	{
		token.type = token_operand; // 操作数
		token.var.type = var_double;
		for (i = 0; isdigit(*e) || *e == '.'; i++)
		{
			s[i] = *e;
			e++;
		}
		s[i] = 0;
		if (sscanf(s, "%lf", &token.var.i) != 1)
		{
			// Can't Read
			goto errorhandler;
		}
	}
	else
	{
		token.type = token_operator; // 操作符
		switch (*e)
		{
		case '(':
			token.ator = operators[oper_lparen];
			break;
		case ')':
			token.ator = operators[oper_rparen];
			break;
		case '+': // 前一个必须是操作数，获取是操作符，但是是右括号
			if (before.type == token_operand || (before.type == token_operator && before.ator.oper == oper_rparen))
			{
				token.ator = operators[oper_plus]; // +
			}
			else
			{
				token.ator = operators[oper_positive]; // 正号
			}
			break;
		case '-':
			if (before.type == token_operand || (before.type == token_operator && before.ator.oper == oper_rparen))
			{
				token.ator = operators[oper_minus]; // 减
			}
			else
			{
				token.ator = operators[oper_negative]; // 负号
			}
			break;
		case '*':
			token.ator = operators[oper_multiply];
			break;
		case '/':
			token.ator = operators[oper_divide];
			break;
		case '%':
			token.ator = operators[oper_mod];
			break;
		case '^':
			token.ator = operators[oper_power];
			break;
		case '!':
			token.ator = operators[oper_factorial];
			break;
		case '=':
			token.ator = operators[oper_eq];
			break;
		case '>':
			if (*(e + 1) == '=')
			{
				token.ator = operators[oper_ge]; // >=
				e++;
			}
			else
			{
				token.ator = operators[oper_gt]; // >
			}
			break;
		case '<':
			if (*(e + 1) == '=') // <=
			{
				token.ator = operators[oper_le];
				e++;
			}
			else if (*(e + 1) == '>') // <>
			{
				token.ator = operators[oper_ne];
				e++;
			}
			else // <
			{
				token.ator = operators[oper_lt];
			}
			break;
		default:
			// Error
			goto errorhandler;
		}
		e++;
	}
	before = token; // 赋值给全局变量

	return token; // 返回

errorhandler:
	memset(&token, 0, sizeof(token));
	fprintf(stderr, "表达式 %s 前有语法错误！不可识别的运算符！\n", h);
	exit(EXIT_FAILURE);
}

PTLIST infix2postfix()
{
	PTLIST list = NULL, tail, p; // list 保存表达式操作数和操作符，tail始终指向列表最后一个元素，p临时变量
	PTLIST stack = NULL; // 保存操作符

	stack = (PTLIST)calloc(1, sizeof(TOKEN_LIST)); // 申请一个保存token变量的堆空间
	stack->next = NULL;							   // 下一个初始化NULL
	stack->token.type = token_operator;			   // 类型为操作符
	stack->token.ator = operators[oper_min];	   // 操作符

	memset(&before, 0, sizeof(before)); // before 为全局变量，用于保存之前的操作符
										// 具体作用参看下面的章节
	for (;;)
	{
		p = (PTLIST)calloc(1, sizeof(TOKEN_LIST));
		// calloc 自动初始化
		p->next = NULL;
		p->token = next_token(); // 获取下一个token
		if (p->token.type == token_operand)
		{ // 如果是操作数
			if (!list)
			{					 // 如果list为空
				list = tail = p; // list等于tail等于p
			}
			else
			{					// 否则
				tail->next = p; // tail下一个等于p
				tail = p;		// tail等于p 注意：这个写法有点巧妙，执行这一句之后，&list->next == &tail
			}
		}
		else if (p->token.type == token_operator)
		{ // 如果是操作符
			if (p->token.ator.oper == oper_rparen)
			{			 // 如果是右括号
				free(p); // 右括号可以忽略掉，释放内存
				while (stack->token.ator.oper != oper_lparen)
				{ // 将临时空间里的【操作符】一个个输出，直到碰到左括号为止
					p = stack;
					stack = stack->next;
					tail->next = p; // 下面三行与251行有异曲同工之妙
					tail = p;
					tail->next = NULL;
				}
				p = stack; //
				stack = stack->next;
				free(p); // 左括号可以忽略掉，释放内存
			}
			else
			{
				while (stack->token.ator.isp >= p->token.ator.icp)
				{						 // 正在放入（incoming） 已经放入（in-stack）
					tail->next = stack;	 // 将栈中的值输出
					stack = stack->next; // 栈指向下一个值
					tail = tail->next;	 // 输出链表指向下一个值
					tail->next = NULL;	 // 输出链表下一个设置为空
				}
				p->next = stack; // p的下一个值指向链表
				stack = p;		 // 栈设置为p
			}
		}
		else
		{			 // 未知符号，直接释放内存空间
			free(p); // 变量堆空间用完，记得释放空间
			break;	 // 退出循环
		}
	}
	while (stack) // 遍历栈中所有的值
	{
		p = stack;
		stack = stack->next;				// 栈移动到下一个
		if (p->token.ator.oper != oper_min) // 如果没到栈底
		{
			p->next = NULL; // p下一个值设置为空
			tail->next = p; // 原理同251行
			tail = p;		// 指向尾部元素
		}
		else // 到了栈底，则退出循环
		{
			free(p);
		}
	}

	return list;
}

VARIANT eval(const char expr[])
{
	PTLIST list, p;
	PTLIST stack = NULL, op1, op2;
	STRING s1, s2;
	STRING error_msg = "Error: ";
	VARIANT v;

	strcat(error_msg, expr); // 字符串拼接
	strcat(error_msg, ": ");

	h = e = expr;			// 表达式赋值给全局变量
	list = infix2postfix(); // 中缀表达式转换为后缀表达式
	// 从头开始一个标记（token）一个标记地往后扫描，碰到操作数时先放到一个临时的空间里；
	// 碰到操作符就从空间里取出最后两个操作数，做相应的运算，然后将结果再次放回空间中。
	// 到了最后，空间中就只剩下操作数即运算结果！
	while (list)
	{
		p = list; // 指向头元素
		list = list->next; // 指向下一个元素

		if (p->token.type == token_operand) // 如果是操作数
		{
			p->next = stack; // 则下一个元素设置为stack
			stack = p; // stack设置为p
			continue;
		}

		assert(stack != NULL); // stack等于NULL则报错

		// 操作符
		switch (p->token.ator.oper)
		{
		/* 算数运算 */
		case oper_plus:
			op2 = stack; // 取两个操作数
			op1 = stack = stack->next;

			if (op1->token.var.type == var_double &&
				op2->token.var.type == var_double)
			{											// 如果是数字类型
				op1->token.var.i += op2->token.var.i;
			}
			else										// 字符串类型
			{
				if (op1->token.var.type == var_double)	// 
				{
					sprintf(s1, "%g", op1->token.var.i);
				}
				else
				{
					strcpy(s1, op1->token.var.s);
				}
				if (op2->token.var.type == var_double)
				{
					sprintf(s2, "%g", op2->token.var.i);
				}
				else
				{
					strcpy(s2, op2->token.var.s);
				}
				op1->token.type = var_string;
				strcat(s1, s2);
				strcpy(op1->token.var.s, s1);
			}
			free(op2);
			break;
		case oper_minus:								// 减法
			op2 = stack;
			op1 = stack = stack->next;

			if (op1->token.var.type == var_double &&
				op2->token.var.type == var_double)
			{
				op1->token.var.i -= op2->token.var.i;
				free(op2);
			}
			else
			{
				// Error
				strcat(error_msg, "字符串不支持减运算\n");
				goto errorhandler;
			}
			break;
		case oper_multiply:								// 乘法
			op2 = stack;
			op1 = stack = stack->next;

			if (op1->token.var.type == var_double &&
				op2->token.var.type == var_double)
			{
				op1->token.var.i *= op2->token.var.i;
				free(op2);
			}
			else
			{
				// Error
				strcat(error_msg, "字符串不支持乘运算\n");
				goto errorhandler;
			}
			break;
		case oper_divide:								// 除法
			op2 = stack;
			op1 = stack = stack->next;

			if (op1->token.var.type == var_double &&
				op2->token.var.type == var_double)
			{
				if (fabs(op2->token.var.i) < 1E-6)
				{
					// Error
					strcat(error_msg, "除数为 0\n");
					goto errorhandler;
				}
				else
				{
					op1->token.var.i /= op2->token.var.i;
					free(op2);
				}
			}
			else
			{
				// Error
				strcat(error_msg, "字符串不支持除运算\n");
				goto errorhandler;
			}
			break;
		case oper_mod:									// 取模
			op2 = stack;
			op1 = stack = stack->next;

			if (op1->token.var.type == var_double &&
				op2->token.var.type == var_double)
			{
				if (fabs(op2->token.var.i) < 1E-6)
				{
					// Error
					strcat(error_msg, "除数为 0\n");
					goto errorhandler;
				}
				else
				{
					int a = (int)op1->token.var.i;
					int b = (int)op2->token.var.i;
					op1->token.var.i = a % b;
					free(op2);
				}
			}
			else
			{
				// Error
				strcat(error_msg, "字符串不支持求模运算\n");
				goto errorhandler;
			}
			break;
		case oper_power:								// 平方
			op2 = stack;
			op1 = stack = stack->next;

			if (op1->token.var.type == var_double &&
				op2->token.var.type == var_double)
			{
				op1->token.var.i = pow(op1->token.var.i,
									   op2->token.var.i);
				free(op2);
			}
			else
			{
				// Error
				strcat(error_msg, "字符串不支持幂运算\n");
				goto errorhandler;
			}
			break;
		case oper_positive:								// 取正值
			// Ignored
			break;
		case oper_negative:								// 取负值
			if (stack->token.var.type == var_double)
			{
				stack->token.var.i = -stack->token.var.i;
			}
			else
			{
				// 字符串取反操作
				STRING s;
				char *p = stack->token.var.s;
				int len = (int)strlen(p);
				int i;
				for (i = 0; i < len; i++)
				{
					s[i] = *(p + len - i - 1);
				}
				s[i] = 0;
				strcpy(p, s);
			}
			break;
		case oper_factorial:
			if (stack->token.var.type == var_double)
			{
				int i = (int)stack->token.var.i;
				stack->token.var.i = 1;
				while (i > 1)
				{
					stack->token.var.i *= i;
					i--;
				}
			}
			else
			{
				// Error
				strcat(error_msg, "字符串不支持阶乘运算\n");
				goto errorhandler;
			}
			break;
		/* 关系运算 */
		case oper_lt:
		case oper_gt:
		case oper_eq:
		case oper_ne:
		case oper_le:
		case oper_ge:
			op2 = stack;
			op1 = stack = stack->next;

			if (op1->token.var.type == var_double &&
				op2->token.var.type == var_double)
			{
				switch (p->token.ator.oper)
				{
				case oper_lt:
					op1->token.var.i = op1->token.var.i < op2->token.var.i;
					break;
				case oper_gt:
					op1->token.var.i = op1->token.var.i > op2->token.var.i;
					break;
				case oper_eq:
					op1->token.var.i = op1->token.var.i == op2->token.var.i;
					break;
				case oper_ne:
					op1->token.var.i = op1->token.var.i != op2->token.var.i;
					break;
				case oper_le:
					op1->token.var.i = op1->token.var.i <= op2->token.var.i;
					break;
				case oper_ge:
					op1->token.var.i = op1->token.var.i >= op2->token.var.i;
					break;
				}
			}
			else
			{
				if (op1->token.var.type == var_double)
				{
					sprintf(s1, "%g", op1->token.var.i);
				}
				else
				{
					strcpy(s1, op1->token.var.s);
				}
				if (op2->token.var.type == var_double)
				{
					sprintf(s2, "%g", op2->token.var.i);
				}
				else
				{
					strcpy(s2, op2->token.var.s);
				}
				op1->token.var.type = var_double;
				switch (p->token.ator.oper)
				{
				case oper_lt:
					op1->token.var.i = strcmp(op1->token.var.s, op2->token.var.s) < 0;
					break;
				case oper_gt:
					op1->token.var.i = strcmp(op1->token.var.s, op2->token.var.s) > 0;
					break;
				case oper_eq:
					op1->token.var.i = strcmp(op1->token.var.s, op2->token.var.s) == 0;
					break;
				case oper_ne:
					op1->token.var.i = strcmp(op1->token.var.s, op2->token.var.s) != 0;
					break;
				case oper_le:
					op1->token.var.i = strcmp(op1->token.var.s, op2->token.var.s) <= 0;
					break;
				case oper_ge:
					op1->token.var.i = strcmp(op1->token.var.s, op2->token.var.s) >= 0;
					break;
				}
			}
			free(op2);
			break;
		/* 逻辑运算 */
		case oper_and:
		case oper_or:
		{
			int b1 = 0, b2 = 0;

			op2 = stack;
			op1 = stack = stack->next;

			if (op1->token.var.type == var_double)
			{
				b1 = fabs(op1->token.var.i) > 1E-6;
			}
			else
			{
				b1 = op1->token.var.s[0] != 0;
			}
			if (op2->token.var.type == var_double)
			{
				b2 = fabs(op2->token.var.i) > 1E-6;
			}
			else
			{
				b2 = op2->token.var.s[0] != 0;
			}

			switch (p->token.ator.oper)
			{
			case oper_and:
				op1->token.var.i = b1 && b2;
				break;
			case oper_or:
				op1->token.var.i = b1 || b2;
				break;
			}

			free(op2);
			break;
		}
		case oper_not:
			op1 = stack;
			if (op1->token.var.type == var_double)
			{
				op1->token.var.i = fabs(op1->token.var.i) < 1E-6;
			}
			else
			{
				op1->token.var.i = op1->token.var.s[0] == 0;
			}
			op1->token.var.type = var_double;
			break;
		default:
			// Unbelievable
			strcat(error_msg, "不识别的运算符！\n");
			goto errorhandler;
			break;
		}
		free(p);
	}

	assert(stack && !stack->next);
	v = stack->token.var;
	free(stack);

	return v;

errorhandler:
	perror(error_msg);
	exit(EXIT_FAILURE);
}
